package com.sheng.leetcode.year2022.swordfingeroffer.day20;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/19
 *<p>
 * 剑指 Offer 33. 二叉搜索树的后序遍历序列<p>
 *<p>
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。<p>
 * 如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。<p>
 * 参考以下这颗二叉搜索树：<p>
 *<p>
 *      5<p>
 *     / \<p>
 *    2   6<p>
 *   / \<p>
 *  1   3<p>
 * 示例 1：<p>
 * 输入: [1,6,3,2,5]<p>
 * 输出: false<p>
 * <p>
 * 示例 2：<p>
 * 输入: [1,3,2,6,5]<p>
 * 输出: true<p>
 *<p>
 * 提示：<p>
 *<p>
 * 数组长度 <= 1000<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0033 {

    @Test
    public void test01() {
//        int[] postorder = {1,6,3,2,5};
        int[] postorder = {1,3,2,6,5};
        System.out.println(new Solution33().verifyPostorder(postorder));
    }
}
class Solution33 {
    public boolean verifyPostorder(int[] postorder) {
        return recursion(postorder, 0, postorder.length - 1);
    }

    public boolean recursion(int[] nums, int start, int end) {
        if (start >= end) {
            return true;
        }
        int mid = start;
        // 找到第一个大于根节点的数字的索引
        while (nums[mid] < nums[end]) {
            mid++;
        }
        // 验证后半部分是否满足二叉搜索树的规律
        int checkEnd = mid;
        while(nums[checkEnd] > nums[end]) {
            checkEnd++;
        }
        return end == checkEnd && recursion(nums, start, mid - 1) && recursion(nums, mid, end - 1);
    }
}
